package org.example.myleet.p653;

import org.example.myleet.Utils.TreeNode;

public class Solution {

    public boolean findTarget(TreeNode root, int k) {
        return dfs(root, root, k);
    }

    private boolean dfs(TreeNode root, TreeNode node, int k) {
        int val = k - node.val;
        if (val != node.val && findValue(root, val)) {
            return true;
        }
        boolean found = false;
        if (null != node.left) {
            found = dfs(root, node.left, k);
        }
        if (found) {
            return true;
        }
        if (null != node.right) {
            found = dfs(root, node.right, k);
        }
        return found;
    }

    private boolean findValue(TreeNode node, int val) {
        if (val < node.val) {
            if (null == node.left) {
                return false;
            }
            return findValue(node.left, val);
        } else if (val > node.val) {
            if (null == node.right) {
                return false;
            }
            return findValue(node.right, val);
        } else {
            return true;
        }
    }
}
